import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86187
 * Date: 2022-10-15
 * Time: 22:07
 */
public class Solution {

    // 思路三: 双倍串.
    public static String LeftRotateString3(String str,int n) {
        if(n <= 0 || str == null || str.length() <= 1)
            return str;

        int length = str.length();
        int step = n % length;

        StringBuilder sb = new StringBuilder(str+str);
        return sb.substring(step,step+length);
    }

    /**
     *  思路二: 局部逆置，在整体逆置.
     *  时间复杂度: O(N)
     */
    public static String LeftRotateString2(String str,int n) {
        if(n <= 0 || str == null || str.length() <= 1)
            return str;

        int length = str.length();
        int step = n % length;
        char[] s = str.toCharArray();

        reserveString(s,0,step-1);
        reserveString(s,step,length-1);
        reserveString(s,0,length-1);

        return new String(s);
    }
    private static void reserveString(char[] str,int start, int end) {
        while(start < end) {
            char ch = str[start];
            str[start] = str[end];
            str[end] = ch;

            ++start;
            --end;
        }
    }

    /**
     * 思路一: 保存第一个，剩下的整体前移一个，第一个放在最后，完成一次移动，一次能移动，多次也可以.
     *      时间复杂度: O(N*step).
     */
    public static String LeftRotateString(String str,int n) {
        if(n <= 0 || str == null || str.length() <= 1)
            return str;

        int length = str.length();
        int step = n % length;
        char[] s = str.toCharArray();

        while(step > 0) {
            LeftRotateStringHelper(s);
            --step;
        }

        return new String(s);
    }
    private static void LeftRotateStringHelper(char[] str) {
        char ch = str[0];
        int length = str.length;

        // for(int i = 0; i < length - 1; ++i) {
        //            str[i] = str[i+1];
        // }
        System.arraycopy(str, 1, str, 0, length - 1);
        str[length-1] = ch;
    }

    public static void main(String[] args) {
        String str = "123456789";

        System.out.println(LeftRotateString(str, 4));
        System.out.println(LeftRotateString2(str, 4));
        System.out.println(LeftRotateString3(str, 4));

    }
}
